/**
 * @Title:ImproveB.java
 * @Description:TODO
 * @author shan
 * @date 2015-4-11 上午9:57:59
 */
package com.shan.ai.combo.impl;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ThreadPoolExecutor;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import com.shan.ai.combo.BaseCombo;
import com.shan.ai.combo.ICombo;
import com.shan.ai.combo.IComboConstant;

/**
 * @author ShanSheng
 * 
 */
public class ImproveC extends BaseCombo implements ICombo, IComboConstant {

    private ThreadPoolExecutor executor = null;

    private Lock lock;

    /**
     * 全局终止条件标识
     */
    private AtomicBoolean g_FinalStop;

    public long count;

    /**
     * 全局最大COST值
     */
    private volatile double g_maxCost;

    private final int CORE_SIZE = 4;
    private final int MAX_CORE_SIZE = 4;
    private final long KEEP_ALIVE_TIME = 10;
    private final TimeUnit TIME_UNIT = TimeUnit.SECONDS;
    private final BlockingQueue<Runnable> WORKING_QUEUE = new ArrayBlockingQueue<Runnable>(30);

    public enum Direct {
        up, down, left, right
        // ,up_left,up_right,down_left,down_right
    }

    /**
     * @param args
     */
    public static void main(String[] args) {

        ImproveC board = new ImproveC();

        long t1 = System.currentTimeMillis();

        // board.genRandomBoard();

        board.printBorad(board.initBeads);

        board.move(board.initBeads);

        // board.printList();

        // board.printBorad(board.maxBeads);
        // // board.computeCombo(board.maxBeads);
        //
        long t2 = System.currentTimeMillis();

        System.out.println("Time(s):" + (t2 - t1));
        // System.out.println("Combo:" + board.comboList.size());
        System.out.println("Move:" + board.count);
        System.out.println("Cost(s):" + board.g_maxCost);

        for (int i = 0; i < board.maxStepList.size(); i++) {
            System.out.print(board.maxStepList.get(i) + "->");
        }

        System.out.println();

        board.printBorad(board.maxBeads);

        for (BeadList combo : board.maxcomboList) {
            System.out.print(combo.type + "=");
            for (int i = 0; i < combo.size(); i++) {
                System.out.print(combo.get(i) + "->");
            }
            System.out.println();
        }

        ScreenParser.drawLines(board.maxStepList, uuid + "_" + String.valueOf(board.g_maxCost));
        ScreenParser.drawLinesOnDevice(board.maxStepList);

    }

    /**
     * 构造函数初始化
     */
    public ImproveC() {
        // 此处重复init了，Base的构造函数已经处理了
        // initBeads = initBoard();
        startTime = System.currentTimeMillis();
        g_FinalStop = new AtomicBoolean(false);
        g_maxCost = 1;
        count = 0;
        lock = new ReentrantLock();
    }

    /**
     * 开始移动 重载：使用多线程从不同的点开始移动
     */
    @Override
    public List<Point> move(BeadType[][] initBeads) {
        startTime = System.currentTimeMillis();

        executor = new ThreadPoolExecutor(CORE_SIZE, MAX_CORE_SIZE, KEEP_ALIVE_TIME, TIME_UNIT, WORKING_QUEUE);

        for (int i = MAX_ROW - 1; i >= 0; i--) {
            for (int j = 0; j < MAX_COLUMN; j++) {

                // runTimeBeads = copyBoard(initBeads);

                Point startPoint = new Point(i, j);
                executor.execute(new WorkThread4ImproveC(startPoint, initBeads));

            }
        }

        executor.shutdown();

        try {
            boolean loop = true;
            do { // 等待所有任务完成
                loop = !executor.isTerminated(); // 阻塞，直到线程池里所有任务结束

                Thread.sleep(2000);
                if (g_FinalStop.get()) {
                    executor.shutdownNow();
                    System.out.println("ShutDown Now!");
                }
            } while (loop);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        return maxStepList;
    }

    class WorkThread4ImproveC implements Runnable {

        private Point startPoint;
        private BeadType[][] runTimeBeads;
        private List<Point> stepList;

        // private List<Point> maxStepList;
        // private List<BeadList> maxcomboList;

        public WorkThread4ImproveC(Point startPoint, BeadType[][] initBeads) {
            this.startPoint = startPoint;
            stepList = new ArrayList<Point>();
            runTimeBeads = copyBoard(initBeads);
            // maxcomboList = new ArrayList<BeadList>();

        }

        /*
         * (non-Javadoc)
         * 
         * @see java.lang.Runnable#run()
         */
        @Override
        public void run() {
            Thread.currentThread().setName("[" + startPoint.x + "," + startPoint.y + "]");
            // System.out.println(Thread.currentThread().getName() + "=Start");

            stepList.add(startPoint);

            moveIn(-1);

            // System.out.println(Thread.currentThread().getName() + "=Cost(s):"
            // + (System.currentTimeMillis() - t1));
            System.out.println(Thread.currentThread().getName() + "=End at(s):"
                    + (System.currentTimeMillis() - startTime));
            // System.out.println(Thread.currentThread().getName() + "=Combo:" +
            // maxcomboList.size());
            // System.out.println(Thread.currentThread().getName() + "=Value:" +
            // maxCost);
            // System.out.println(Thread.currentThread().getName() + "=End" );

        }

        /**
         * 移动到递归的下一步
         * 
         * @param lastCost
         *            移动前的cost
         */
        public void moveIn(double lastCost) {

            if (g_FinalStop.get()) {
                return;
            }

            // 终止条件满足
            if (isEndCondition()) {
                g_FinalStop.set(true);
                return;
            }

            if (stepList.size() >= MAX_STEP) {
                // bOnceStop = true;
                moveBack();

                return;
            }

            Point currPoint = stepList.get(stepList.size() - 1);

            for (Direct direct : Direct.values()) {

                // if(direct.ordinal() > 3){
                // continue;
                // }

                double currCost = moveAndcost(currPoint, direct);
                // printList();
                // cost大于0代表移动有效。当移动两步时，如果还没有产生Combo，则退回。
                // 认定前两步移动能够产生Comobo才有可能是最优解。
                // 移动4个还没有Combo，则认为应该从其它位置的珠子起手；或者移动4个珠子之后，后面的移动会导致cost降低则回退
                if ((currCost >= 0 && stepList.size() < 4)
                        || (currCost > 0 && stepList.size() >= 4 && currCost >= lastCost)) {
                    // if ((currCost >= 0 && stepList.size() < 4) || (currCost >
                    // 0 && stepList.size() >= 4) ) {
                    moveIn(currCost);
                    if (g_FinalStop.get()) {
                        return;
                    }
                    // resetBoard();
                }
                // currCost小于0，代表移动方向非法，没有产生真正的移动
                else if (currCost >= 0) {
                    // 回退并尝试下一个方向
                    moveBack();
                }

            }

            moveBack();

            return;
        }

        /**
         * 回退一步
         */
        public void moveBack() {
            // 如果只有一步，则不执行回退。
            if (stepList.size() < 2) {
                // bOnceStop = true;
                return;
            }
            Point from = stepList.remove(stepList.size() - 1);
            Point to = stepList.get(stepList.size() - 1);

            BeadType temp = runTimeBeads[from.x][from.y];
            runTimeBeads[from.x][from.y] = runTimeBeads[to.x][to.y];
            runTimeBeads[to.x][to.y] = temp;
        }

        public boolean isEndCondition() {
            if (g_maxCost > MAX_COST) {
                System.out.println("局面值达到");
                return true;
            }

            if (System.currentTimeMillis() - startTime > OVER_TIME) {
                System.out.println("时间达到");
                return true;
            }

            return false;
        }

        /**
         * 从指定点开始向指定方向移动
         * 
         * @param from
         *            指定点
         * @param direct
         *            指定方向
         * @return >=0 移动后的局面cost值 <0 非法移动，没有真正产生移动
         */
        public double moveAndcost(Point from, Direct direct) {

            // if(stepList.size() >= MAX_STEP){
            // cost = -1;
            // return;
            // }

            Point to = null;
            switch (direct) {
            case up:
                to = new Point(from.x - 1, from.y);
                break;
            case down:
                to = new Point(from.x + 1, from.y);
                break;
            case left:
                to = new Point(from.x, from.y - 1);
                break;
            case right:
                to = new Point(from.x, from.y + 1);
                break;
            // 不支持斜向移动
            // case up_left:
            // to = new Point(from.x-1, from.y - 1);
            // break;
            // case up_right:
            // to = new Point(from.x-1, from.y + 1);
            // break;
            // case down_left:
            // to = new Point(from.x+1, from.y - 1);
            // break;
            // case down_right:
            // to = new Point(from.x+1, from.y+ 1);
            // break;

            default:
                break;
            }

            if (to.x < 0 || to.x >= MAX_ROW || to.y < 0 || to.y >= MAX_COLUMN) {
                // cost = -1;
                return -1;
            }

            if (stepList.contains(to)) {
                return -1;
            }

            count++;

            // if (count.get() % 1000000 == 0) {
            // System.out.println("Move:" + count);
            // }

            // recordBoard();
            stepList.add(to);

            BeadType temp = runTimeBeads[from.x][from.y];
            runTimeBeads[from.x][from.y] = runTimeBeads[to.x][to.y];
            runTimeBeads[to.x][to.y] = temp;

            // recordBoard();
            List<BeadList> comboList = computeCombo(runTimeBeads);
            double cost = computeCost(comboList);

            if ((cost > g_maxCost || (maxStepList != null && cost == g_maxCost && stepList.size() < maxStepList.size()))
                    && filterLink(comboList)) {
                lock.lock();

                try {
                    g_maxCost = cost;
                    maxStepList = new ArrayList<IComboConstant.Point>(stepList);
                    maxcomboList = new ArrayList<IComboConstant.BeadList>(comboList);
                    System.out.println(Thread.currentThread().getName() + "=Update Max Cost:" + cost + " ["
                            + (System.currentTimeMillis() - startTime) + "] Combo:" + maxcomboList.size());
                    // printList();

                    maxBeads = copyBoard(runTimeBeads);
                } finally {
                    lock.unlock();
                }

                // printBorad();

            }
            // printBorad();

            // resetBoard();

            // printList();
            // printBorad();
            return cost;
        }

        public boolean filterLink(List<BeadList> list) {

            int bFire = 0;
            int bWater = 0;
            int bWood = 0;
            int bHeart = 0;
            int bLight = 0;
            int bDark = 0;
            Set typeSet = new HashSet<BeadType>();
            for (BeadList beadList : list) {

                typeSet.add(beadList.type);

                if (beadList.type == BeadType.fire) {// && beadList.size()>=5
                    bFire += beadList.size();

                }
                if (beadList.type == BeadType.water) {
                    bWater += beadList.size();
                }
                if (beadList.type == BeadType.wood) {
                    bWood += beadList.size();
                }
                if (beadList.type == BeadType.heart) {
                    bHeart += beadList.size();
                }
                if (beadList.type == BeadType.light) {
                    bLight += beadList.size();
                }
                if (beadList.type == BeadType.dark) {
                    bDark += beadList.size();
                }
            }

            if (bHeart < 3) {
                // return false;
            }

            if (bFire > 0 && bWater > 0 && bWood > 0 && bLight > 0) {
                return true;
            }
            if (bWater > 0 && bWood > 0 && bDark > 0) {
                // return true;
            }
            return true;
        }
    }

}
